package com.labuladong.sort;

import java.util.Random;

class QuickSort {
    public static void sort(int[] nums) {
        // 为了避免出现耗时的极端情况，先随机打乱数组元素顺序
        shuffle(nums);
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }
 
    // 私有的递归排序函数，使用快速排序算法对数组进行排序 
    private static void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return; // 递归结束条件，当 lo 大于等于 hi 时，子数组已经有序
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        int p = partition(nums, lo, hi); // 获取切分点 p
 
        // 对切分点左右两边的子数组分别进行递归排序
        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }
 
    // 切分函数，用于确定切分点并重新排列数组元素
    private static int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo]; // 选择第一个元素作为切分元素
        int i = lo + 1, j = hi; // 定义两个指针 i 和 j
 
        // 使用双指针将数组划分为两部分，一部分小于等于pivot，一部分大于pivot
        while (i <= j) {
            while (i < hi && nums[i] <= pivot) {
                i++; // 移动左指针直到找到一个大于pivot的元素
            }
            while (j > lo && nums[j] > pivot) {
                j--; // 移动右指针直到找到一个小于等于pivot的元素
            }
            // 交换左右指针所指向的元素，保证左边小于等于pivot，右边大于pivot
            if (i >= j) {
                break; // 当左右指针相遇时退出循环
            }
            swap(nums, i, j); // 交换 nums[i] 和 nums[j]
        }
        // 将pivot放到合适的位置，即使得左边元素小于等于pivot，右边元素大于pivot
        swap(nums, lo, j); // 将切分元素放到最终位置
        return j; // 返回切分元素的下标
    }
 
    // 洗牌算法，将输入的数组随机打乱
    private static void shuffle(int[] nums) {
        Random rand = new Random(); // 创建随机数生成器
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i); // 生成 [i, n - 1] 范围内的随机数
            swap(nums, i, r); // 将第i个元素与第r个元素交换
        }
    }
 
    // 原地交换数组中的两个元素
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i]; // 临时保存 nums[i]
        nums[i] = nums[j];  // 将 nums[j] 放到 nums[i] 的位置
        nums[j] = temp;      // 将临时保存的 nums[i] 放到 nums[j] 的位置
    }
}